package com.guaoran.algorithm.node.list;

import com.guaoran.algorithm.entity.Node;
import com.guaoran.algorithm.entity.NodeList;

/**
 * @Auth gucheng
 * @Desc  链表相加
 * @Date 2020/12/18 下午6:11
 */
public class AddTwoNumbers {
    public static void main(String[] args) {
//        NodeList<Integer> nodeList = new NodeList<>();
//        nodeList.add(2);
//        nodeList.add(4);
//        nodeList.add(3);
//        NodeList<Integer> nodeList2 = new NodeList<>();
//        nodeList2.add(5);
//        nodeList2.add(6);
//        nodeList2.add(4);
//        System.out.println(addTwoNumbers(nodeList.head, nodeList2.head));

        NodeList<Integer> nodeList = new NodeList<>();
        nodeList.add(7);
        nodeList.add(2);
        nodeList.add(4);
        nodeList.add(3);
        NodeList<Integer> nodeList2 = new NodeList<>();
        nodeList2.add(5);
        nodeList2.add(6);
        nodeList2.add(4);

        System.out.println(addTwoNumbers2(nodeList.head, nodeList2.head));

    }

    /**
     * 链表相加
     *  2 -> 4 -> 3
     *  +
     *  5 -> 6 -> 4
     *  =
     *  7 -> 0 -> 8
     * @param head
     * @param head2
     * https://leetcode.com/problems/add-two-numbers/
     * @return
     */
    private static Node addTwoNumbers(Node<Integer> head, Node<Integer> head2) {
        if(head == null && head2 == null){
            return null;
        }
        if(head == null){
            return head2;
        }
        if(head2 == null){
            return head;
        }
        Node sum = new Node(-1);
        Node temp = sum;
        int rel = 0;// 进数
        while(head != null && head2 != null){
            int val = head.data+head2.data+rel;
            rel = val/10;
            Node node = new Node(val%10);
            temp.next = node;
            temp = temp.next;
            head = head.next;
            head2 = head2.next;
        }

        while (head != null){
            int val = head.data+rel;
            rel = val/10;
            Node node = new Node(val%10);
            temp.next = node;
            temp = temp.next;
            head = head.next;
        }
        while (head2 != null){
            int val = head2.data+rel;
            rel = val/10;
            Node node = new Node(val%10);
            temp.next = node;
            temp = temp.next;
            head2 = head2.next;
        }

        if(rel!=0){
            Node node = new Node(rel);
            temp.next = node;
        }
        Node result = sum.next;
        System.out.println(result);
        return result;
    }


    /**
     * 链表 相加
     *  7 -> 2 -> 4 -> 3
     *  +
     *       5 -> 6 -> 4
     *  =
     *  7 -> 8 -> 0 -> 7
     * @param l1
     * @param l2
     * https://leetcode.com/problems/add-two-numbers-ii/
     * @return
     */
    private static Node addTwoNumbers2(Node<Integer> l1,Node<Integer> l2){
        if(l1==null && l2==null) return null;
        if(l1==null) return l2;
        if(l2==null) return l1;

        // 分别获取每个元素的长度
        int length1 = size(l1);
        int length2 = size(l2);

        // 获取链表相加的值 ，组装成一个新的链表 ，这里不做满十进一，且逆向存储
        // 7 -> 2 -> 4 -> 3
        // +
        //      5 -> 6 -> 4
        // =
        // 7 -> 10 -> 7 -> 7
        // 用来计算结果
        Node<Integer> reverseHead = null;
        // 用来创建新的数据
        Node<Integer> temp;
        // 当l1 的元素长度大于 l2 的元素长度时
        // 先计算出大于的前部分的值
        while(l1 != null || l2 !=null){
            if(length1>length2){
                temp = new Node(l1.data);
                l1 = l1.next;
                length1 --;
            }else if(length2>length1){
                temp = new Node(l2.data);
                l2 = l2.next;
                length2 --;
            }else{
                // l2 等于 l1
                temp = new Node(l1.data+l2.data);
                l1 = l1.next;
                l2 = l2.next;
                length1 --;
                length2 --;
            }
            // 将最新的节点添加到链表最前面
            temp.next = reverseHead;
            reverseHead = temp;
        }
        // 将计算过的元素进行满十进一操作，且进行逆向存储
        // 7 -> 10 -> 7 -> 7
        // ==> 满十进一
        // 7 -> 0 -> 8 -> 7
        // ==> 翻转，因为在第一步进行了翻转，否则不好进行满十进一
        // 7 -> 8 -> 0 -> 7
        // 进数
        int rel = 0;
        // 将大于等于10 的元素进行进位
        Node<Integer> node = reverseHead;
        Node<Integer> newHead = null;
        while(node != null){
            Integer data = node.data + rel;
            temp = new Node(data%10);
            rel = data/10;
            // 在前面添加元素
            temp.next = newHead;
            newHead = temp;
            node = node.next;
        }
        if(rel !=0){
            temp = new Node(rel);
            temp.next = newHead;
            newHead = temp;
        }
        return newHead;
    }


    private static int size(Node l) {
        int s = 0;
        while (l != null) {
            l = l.next;
            s++;
        }
        return s;
    }
}
